package com.monkeyboy.array;

/**
 * 二维数组查找元素
 * 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
 *
 * 解题思路就是从右上角开始寻找，如果大就往下寻找，如果小就往作寻找
 * @Author Gavin
 * @date 2021.03.29 10:19
 */
public class TwoArrayFindNums {
    public boolean find(int target, int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int r = 0, c = cols - 1;//从右上角开始
        /**
         * 临界值条件分析：
         * 先是从r=0，c=cols-1开始，也就第一行最后一列开始作为起点
         * 循环期间r作为行是不断往下，c作为列不断往左，所以结束条件就是r行小于等于二维数组的行rows-1,
         * 列不断减小大于等于0就满足
         */
        while (r <= rows - 1 && c >= 0) {
            if (target == matrix[r][c]) {
                return true;
            } else if (target > matrix[r][c]) {
                r++; //目标值大于就往下寻找
            } else {
                c--;//目标值小就往左寻找
            }
        }
        return false;
    }

    public static void main(String[] args) {

    }
}
